\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  将 \(u->v\) 路径上的点全部赋值为 \(w\)
\item
  将 \(u->v\) 路径上的点全部加上 \(w\)
\item
  将 \(u->v\) 路径上的点全部乘上 \(w\)
\item
  \(u->v\) 路径上的点的立方和
\end{itemize}

\begin{lstlisting}
const int N = 1e5+5;
typedef long long LL;
const int p = 1e9 + 7;
int tot, num;
int n, m, r,t,cases=0;

int w[N], a[N], sum1[N * 4], sum2[N * 4], sum3[N * 4], lazy_mul[N * 4], lazy_add[N * 4]; // w[i]=j表示时间戳为i的点的值为j，a[]输入每个节点的值，dat线段树每个点权值，lazy线段树每个点的懒标记
//int h[N], e[N * 2], ne[N * 2], idx;   // 邻接表数组
int dep[N], dfn[N], wson[N], sz[N], top[N], fa[N]; //  dep深度   dfn搜索序 wson重儿子 size子树大小 top链头  fa父节点
vector<int> mp[N];

// 得到sz, fa, dep, wson数组
void dfs1(int u) {
	dep[u] = dep[fa[u]]+1; 
	sz[u] = 1; 
	for(int i = 0; i<mp[u].size(); i++) {
		int j=mp[u][i]; 
		if(j == fa[u]) continue; 
		fa[j] = u; 
		dfs1(j); 
		sz[u] += sz[j]; 
		if(sz[j] > sz[wson[u]]) wson[u] = j;  // 这里要注意根节点不能设为0，否则根节点的最重链无法更新，始终为0
	}
}
// 得到dfn, top数组 
void dfs2(int u, int nowtop) {
	dfn[u] = ++num; 
	w[num] = a[u]; 
	//以搜索序重排权值
	top[u] = nowtop; 
	if(wson[u]) dfs2(wson[u], nowtop);   // 先搜索重儿子
	for(int i = 0; i<mp[u].size(); i++) {// 然后搜索轻儿子
		int y=mp[u][i]; 
		if(y ==fa[u]||y == wson[u]) continue; 
		dfs2(y, y); 
	}
}
void solve(int rt,int len,int a,int b){   //a为add b为mul
	// 修改乘法和加法标记
	lazy_mul[rt] = 1ll*lazy_mul[rt] * b % p;
	lazy_add[rt] = 1ll*lazy_add[rt] * b % p;
	lazy_add[rt] = ((lazy_add[rt] + a) % p + p) % p;
	// 先维护乘法标记：x^3=>(bx)^3, x^2=>(bx)^2
	if(b!=1){   //先乘后加
		sum1[rt] = 1ll*sum1[rt] * b % p;
		sum2[rt] = (1ll*sum2[rt] * b % p) * b % p;
		sum3[rt] = ((1ll*sum3[rt] * b % p) * b % p) * b % p;
	}
	// 再维护加法标记：(x+a)^3=x^3+3x^2*a+3xa^2+a^3, (x+a)^2=x^2+2xa+a^2
	if(a!=0){
		int a2 = 1ll*a * a % p, a3 = 1ll*a2 * a % p;
		sum3[rt] = ((sum3[rt] + (LL)len * a3 % p) + p) % p;
		sum3[rt] = ((sum3[rt] + 3ll * (LL)sum2[rt] % p * a % p) + p) % p;
		sum3[rt] = ((sum3[rt] + 3ll * (LL)sum1[rt] % p * a2 % p) + p) % p;
		sum2[rt] = ((sum2[rt] + 2ll * (LL)sum1[rt] % p * a % p) + p) % p;
		sum2[rt] = ((sum2[rt] + (LL)len * a2 % p) + p) % p;
		sum1[rt] = ((sum1[rt] + (LL)len * a % p) + p) % p;
	}
}
void pushup(int rt) {
	sum1[rt] = (sum1[rt << 1] + sum1[rt << 1 | 1]) % p;
	sum2[rt] = (sum2[rt << 1] + sum2[rt << 1 | 1]) % p;
	sum3[rt] = (sum3[rt << 1] + sum3[rt << 1 | 1]) % p;
}   
// 建线段树，rt为根，l为rt点管辖的左边界， r为rt点管辖的有边界
void build(int rt, int l, int r) {
	lazy_add[rt] = 0;
	lazy_mul[rt] = 1;
	if(l==r) {
		int temp = w[l];
		sum1[rt] = temp;
		sum2[rt] = (1ll*sum1[rt] * sum1[rt]) % p;
		sum3[rt] = (1ll*sum1[rt] * sum2[rt]) % p;
		return ; 
	}
	int mid=(l + r)>>1; 
	build(rt << 1, l, mid); 
	build(rt << 1 | 1, mid+1, r); 
	pushup(rt);
}

// 下传
void pushdown(int rt, int l, int r) {
	int mid = (l + r) >> 1;
	solve(rt << 1, mid - l + 1, lazy_add[rt], lazy_mul[rt]);
	solve(rt << 1 | 1, r - mid, lazy_add[rt], lazy_mul[rt]);
	lazy_add[rt] = 0;
	lazy_mul[rt] = 1;
}
// rt为根，l为rt点管辖的左边界， r为rt点管辖的有边界， L为需要修改的左区间，R为需要修改的右区间
void modify(int rt, int l, int r, int L, int R, int a,int b) {
	if(L <= l && r <= R) {
		solve(rt, r - l + 1, a, b);
		return ; 
	} 
	pushdown(rt, l, r); 
	int mid = (l + r)>>1; 
	if(L <= mid) modify(rt << 1, l, mid, L, R, a,b); 
	if(mid < R) modify(rt << 1 | 1, mid + 1, r, L, R, a,b); 
	pushup(rt);
}
// rt为根，l为rt点管辖的左边界， r为rt点管辖的有边界， L为需要查询的左区间，R为查询的右区间
int query(int rt, int l, int r, int L, int R) {
	if(L <= l && r <= R) {
		return sum3[rt]; 
	}
	pushdown(rt, l, r); 
	int mid = (l + r)>>1; 
	int ans = 0; 
	if(L <= mid) ans += query(rt << 1, l, mid, L, R), ans %= p; 
	if(mid < R) ans += query(rt << 1 | 1, mid + 1, r, L, R), ans %= p;
	pushup(rt);
	return ans; 
}
// 求树从 x 到 y 结点最短路径上所有节点的值之和
int path_query_Tree(int x, int y) {   
	//两点间的修改
	int ans = 0; 
	while(top[x] != top[y]) {// 把x点和y点整到一条重链上
		if(dep[top[x]] < dep[top[y]]) swap(x, y);   // 让x点为深的那个点
		ans += query(1, 1, n, dfn[top[x]], dfn[x]);   
		ans %= p; 
		x = fa[top[x]];  // x每次跳一条链
	}
	if(dep[x] > dep[y]) swap(x, y);   // 让x成为深度更浅的那个点
	ans += query(1, 1, n, dfn[x], dfn[y]); 
	return ans % p; 
}
// 树上修改 a为add ,b为mul
void path_modify_Tree(int x, int y, int a,int b) {
	//树上两点距离 
	while(top[x] != top[y]) { // 把x点和y点整到一条重链上
		if(dep[top[x]] < dep[top[y]]) swap(x, y); // 让x成为对应的头部深度更大的那个点
		modify(1, 1, n, dfn[top[x]], dfn[x], a,b); // 累加x的所有子树和
		x = fa[top[x]]; // x跳到原来x的头部的父节点
	}
	if(dep[x] > dep[y]) swap(x, y);  // 让x成为深度更浅的那个点
	modify(1, 1, n, dfn[x], dfn[y], a,b); 
}
int main() {
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		cases++;
		// 读入边，建树
		for(int i=1; i<=n; ++i) mp[i].clear(),wson[i]=0;
		//memset(h,  -1,  sizeof h);
		num = 0;
		for(int i=1, x, y; i<n; i++) {
			scanf("%d%d", &x, &y);
			mp[x].push_back(y);
			mp[y].push_back(x); 
		}
		for(int i=1; i<=n; i++) scanf("%d", &a[i]); // 读入每个点的权值
		// 两次dfs把树按照重链剖分
		dfs1(1);   // 得到sz, fa, dep, wson数组
		dfs2(1, 1);   // 得到dfn, top数组
		build(1, 1, n); 
		scanf("%d", &m);  
		printf("Case #%d:\n", cases);
		// m次询问
		for(int i=1, op, x, y, z; i<=m; i++) {
			scanf("%d", &op); 
			if(op == 1) {
				scanf("%d%d%d", &x, &y, &z); 
				path_modify_Tree(x, y, z,0); // 将树从 x到 y 结点最短路径上所有节点的值赋值为z
			}
			else if(op == 2) {
				scanf("%d%d%d", &x, &y, &z); 
				path_modify_Tree(x, y, z,1); // 将树从 x到 y 结点最短路径上所有节点的值加上z
			}
			else if(op == 3) {
				scanf("%d%d%d", &x, &y, &z); 
				path_modify_Tree(x, y, 0,z); // 将树从 x到 y 结点最短路径上所有节点的值乘上z
			}
			else {
				scanf("%d%d", &x,&y); 
				printf("%d\n", path_query_Tree(x,y)); 
			}
		}
	} 
	return 0;
}
\end{lstlisting}

\end{document}
